import java.util.Arrays;
import java.util.Stack;

public class Sort {
    /**直接插入排序
    * 时间复杂度:最坏情况(数据无序)O(n^2)最好情况(数据基本有序)O(n)
    * 空间复杂度:O(1)
    * 稳定性:稳定
     **/
    public static  void insertSort(int[] arr){
        for (int i = 1; i < arr.length; i++) {
            int temp=arr[i];
            int j = i-1;
            for (; j >= 0; j--) {
                if(arr[j]>temp){
                    arr[j+1]=arr[j];
                }else{
                    break;
                }
            }
            arr[j+1]=temp;
        }
    }
    /**希尔排序
     * 时间复杂度:和增量序列有关,一般为O(n^1.3)-O(n^1.5)
     * 空间复杂度:O(1)
     * 稳定性:不稳定
     **/
    private static void shell(int[] arr,int gap) {
        for (int i = gap; i < arr.length; i++) {
            int temp=arr[i];
            int j = i-gap;
            for (; j >= 0; j-=gap) {
                if(arr[j]>temp){
                    arr[j+gap]=arr[j];
                }else{
                    break;
                }
            }
            arr[j+gap]=temp;
        }
    }
    public static void shellSort(int[] arr){
        int gap= arr.length;
        //缩小增量
        while(gap > 1){
            shell(arr,gap);
            gap/=2;
        }
        shell(arr,gap);//最后整体插入排序
    }

    /**
     * 直接选择排序
     * 时间复杂度:O(n^2)
     * 空间复杂度:O(1)
     * 稳定性:不稳定
     */
    public static void selectSort(int[] arr) {
        for(int i = 0;i<arr.length;i++){
            int min=i;//记录最小值下标
            for(int j = i+1;j<arr.length;j++){
                if(arr[min]>arr[j]){
                    min=j;
                }
            }
            int temp=arr[i];
            arr[i]=arr[min];
            arr[min]=temp;
        }
    }

    /**堆排序
     * 时间复杂度:O(n*log n)
     * 空间复杂度:O(1)
     * 稳定性:不稳定
     */
    //大根堆向下调整法
    private static void shiftDown(int[] arr,int root,int len) {
        int parent=root;
        int child=parent*2+1;
        while(child<len){
            //如果有左孩子和右孩子比较左右孩子大小，使child指向大的
            if(child+1<len && arr[child]<arr[child+1]){
                child++;
            }
            //判断是否是大根堆
            if(arr[child]>arr[parent]){
                int temp=arr[parent];
                arr[parent]=arr[child];
                arr[child]=temp;
                //判断完根节点后向下判断整棵树是否都为大根堆
                parent=child;
                child=parent*2+1;
            }else{
                break;//说明是大根堆，不在判断
            }
        }
    }
    //创建堆
    private static void createHeap(int[] arr) {
        for(int p=(arr.length-1-1)/2;p>=0;p--){
            shiftDown(arr,p, arr.length);
        }
    }
    //堆排序
    public static void heapSort(int[] arr){
        createHeap(arr);
        int end = arr.length-1;
        while(end>0){
            int temp=arr[0];
            arr[0]=arr[end];
            arr[end]=temp;
            shiftDown(arr,0,end);
            end--;
        }
    }

    /**冒泡排序
     * 时间复杂度:O(n^2)
     * 空间复杂度:O(1)
     * 稳定性:稳定
     */
    public static void bubbleSort(int[] arr) {
        for(int i =0;i< arr.length-1;i++){
            boolean flag=false;
            for (int j = 0; j < arr.length-1-i; j++) {
                if(arr[j]>arr[j+1]){
                    int temp=arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=temp;
                    flag=true;
                }
            }
            //如果数据有序就不在进行后续排序
            if(!flag){
                break;
            }
        }
    }

    /**快速排序
     * 时间复杂度:数据无序O(n*log n)数据有序O(n^2)
     * 空间复杂度:数据无序O(log n)数据有序O(n)
     * 稳定性:不稳定
     */
    //寻找新基准(Hoare法)
    private static int partition1(int[] arr, int left, int right) {
        int i=left;
        int j=right;
        int pivot=arr[left];
        while(i<j){
            //寻找右边小于基准的元素
            while((i<j)&&(arr[j]>=pivot)){
                j--;
            }
            //寻找左边大于基准的元素
            while((i<j)&&(arr[i]<=pivot)){
                i++;
            }
            //将基准左右两边大小顺序不一致的元素互换
            int temp1=arr[i];
            arr[i]=arr[j];
            arr[j]=temp1;
        }
        //将基准和左右下标相遇的元素互换
        int temp2=arr[i];
        arr[i]=arr[left];
        arr[left]=temp2;
        return i;
    }
    //寻找新基准(挖坑法)
    private static int partition2(int[] arr, int left, int right) {
        int i=left;
        int j=right;
        int pivot=arr[left];//挖坑
        while(i<j){
            //寻找右边小于基准的元素
            while((i<j)&&(arr[j]>=pivot)){
                j--;
            }
            //填坑
            arr[i]=arr[j];
            //寻找左边大于基准的元素
            while((i<j)&&(arr[i]<=pivot)){
                i++;
            }
            //填坑
            arr[j]=arr[i];
        }
        //将基准填入最后left和right相遇的坑中
        arr[i]=pivot;
        return i;
    }
    //寻找新基准(双指针法)
    private static int partition3(int[] arr, int left, int right) {
        int prev=left+1;
        int pivot=arr[left];
        for (int i = left+1; i <= right; i++) {
            if(arr[i]<pivot){
                int temp1=arr[i];
                arr[i]=arr[prev];
                arr[prev]=temp1;
                prev++;
            }
        }
        int temp2=arr[left];
        arr[left]=arr[prev-1];
        arr[prev-1]=temp2;
        return prev-1;
    }
    //二叉树结构排序
    private static void quick(int[] arr,int left,int right) {
        if(left>=right) return;
        //优化思路1:当递归区间小时考虑插入排序(减少递归区间内的运行速度)
        /*
        if(right-left+1<40){
            quick_insertSort(arr,left,right);
            return;
        }
         */
        //优化思路3:三数取中法,求的中间值下标与left交换(减少递归深度)
        int mid=threeOfMidIndex(arr,left,right);
        int temp=arr[left];
        arr[left]=arr[mid];
        arr[mid]=temp;

        int pivot=partition2(arr,left,right);//找基准
        quick(arr,left,pivot-1);//排基准左侧的序列
        quick(arr,pivot+1,right);//排基准左侧的序列
    }
    //快排
    public static void quickSort(int[] arr) {
        quick(arr,0,arr.length-1);
    }
    //快排优化思路1.当递归到小区间时数据趋于有序，使用直接插入排序
    public static  void quick_insertSort(int[] arr,int left,int right){
        for (int i = left+1; i <=right; i++) {
            int temp=arr[i];
            int j = i-1;
            for (; j >= 0; j--) {
                if(arr[j]>temp){
                    arr[j+1]=arr[j];
                }else{
                    break;
                }
            }
            arr[j+1]=temp;
        }
    }
    //优化思路2.随机取基法(以left做key，在[left+1,right]中随机选取下标与left交换位置,多数情况下避免单分支(考验运气))
    //优化思路3.三数取中法([left,right]中取中间值的下标与left交换作为分割基准)
    private static int threeOfMidIndex(int[] arr,int left,int right){
        int mid=left+(right-left)>>>1;
        if(arr[left]<arr[right]){
            if(arr[mid]<arr[left]) return left;
            else if(arr[mid]>arr[right]) return right;
            else return mid;
        }else{
            if(arr[mid]>arr[left]) return left;
            else if(arr[mid]<arr[right]) return right;
            else return mid;
        }
    }
    //快排非递归
    public static void quickSortNonR(int[] arr) {
        Stack<Integer> stack=new Stack<>();
        int left=0;
        int right=arr.length-1;
        int pivot=partition2(arr,left,right);//找基准
        //左侧2个数据及以上
        if(pivot>left+1){
            stack.push(left);
            stack.push(pivot-1);
        }
        //右侧2个数据及以上
        if(pivot<right-1){
            stack.push(pivot+1);
            stack.push(right);
        }
        while(!stack.empty()){
            right=stack.pop();
            left=stack.pop();
            pivot=partition2(arr,left,right);
            //左侧2个数据及以上
            if(pivot>left+1){
                stack.push(left);
                stack.push(pivot-1);
            }
            //右侧2个数据及以上
            if(pivot<right-1){
                stack.push(pivot+1);
                stack.push(right);
            }
        }
    }
    /**归并排序
     * 时间复杂度:O(n*log n)
     * 空间复杂度:O(n)
     * 稳定性:稳定
     */
    //合并
    public static void merge(int[] arr,int left,int mid,int right) {
        int s1=left;
        int e1=mid;
        int s2=mid+1;
        int e2=right;
        int[] tempArr=new int[right-left+1];
        int i=0;//tempArr的下标
        while(s1 <= e1 && s2 <= e2){
            if(arr[s1]<=arr[s2]){
                tempArr[i++]=arr[s1++];
            }else{
                tempArr[i++]=arr[s2++];
            }
        }
        //如果一个数组还有剩余就全放到tempArr里
        while(s1<=e1){
            tempArr[i++]=arr[s1++];
        }
        while(s2<=e2){
            tempArr[i++]=arr[s2++];
        }
        //将归并排好的数据放入原数组对应位置
        for (int j = 0; j < tempArr.length; j++) {
            arr[j+left]=tempArr[j];
        }
    }
    public static void mergeSortInternal(int[] arr,int left,int right) {
        if(left>=right) return;
        int mid=left+((right-left)>>>1);
        mergeSortInternal(arr,left,mid);
        mergeSortInternal(arr,mid+1,right);
        merge(arr,left,mid,right);//合并
    }
    //归并排序
    public static void mergeSort(int[] arr) {
        mergeSortInternal(arr,0,arr.length-1);
    }
    //归并非递归
    public static void mergeSortNonR(int[] arr) {
        int gap=1;
        while(gap< arr.length){
            for (int i = 0; i < arr.length; i+=2*gap) {
                int left=i;
                int mid=left+gap-1;
                //修正mid防止越界
                if(mid>= arr.length){
                    mid= arr.length-1;
                }
                int right=mid+gap;
                //修正right防止越界
                if(right>= arr.length){
                    right= arr.length-1;
                }
                merge(arr,left,mid,right);
            }
            gap*=2;
        }
    }
    //非比较排序
    /** 计数排序
     * 时间复杂度:O(数据范围+n)
     * 空间复杂度:O(数据范围)
     * 稳定性:稳定(本写法不一定稳定)
     */
    public static void countSort(int[] arr) {
        //获得最大值和最小值
        int maxVal=arr[0];
        int minVal=arr[0];
        for (int i = 1; i < arr.length; i++) {
            if(arr[i]<minVal){
                minVal=arr[i];
            }
            if(arr[i]>maxVal){
                maxVal=arr[i];
            }
        }
        //计数数组(数据放到对应位置,值表示出现的次数)
        int[] countArr=new int[maxVal-minVal+1];
        for (int i = 0; i < arr.length; i++) {
            countArr[arr[i]-minVal]++;
        }
        //将计数数组对应数据放回原数组
        int index=0;
        for (int i = 0; i < countArr.length; i++) {
            while(countArr[i]>0){
                arr[index++]=i+minVal;
                countArr[i]--;
            }
        }
    }
    /**基数排序
     * 时间复杂度:
     * 空间复杂度:
     * 稳定性:
     **/
    public static void main(String[] args) {
        int[] array={5,10,3,8,2};
        System.out.println("排序前:"+ Arrays.toString(array));
//        insertSort(array);//直接插入排序
//        shellSort(array);//希尔排序
//        selectSort(array);//直接选择排序
//        heapSort(array);//堆排序
//        bubbleSort(array);//冒泡排序
//        quickSort(array);//快排递归
//        quickSortNonR(array);//快排非递归
//        mergeSort(array);//归并排序
//        mergeSortNonR(array);//归并非递归
        countSort(array);//计数排序
        System.out.println("排序后:"+Arrays.toString(array));

    }

}
